package mytest;

public class Test_rmq {

	static int[] S={1,1000,4,2,3,5,7,-18,1290,12,2,1,6};
	
	static int N=S.length,len=(int)(Math.log(N)/Math.log(2));
	
	static int Max[][]=new int[N][len+1];
	static int Min[][]=new int[N][len+1];
	static void init()
	{
		for(int i=0;i<N;i++)
		{
			Max[i][0]=i;
			Min[i][0]=i;
		}
		for(int i=1;(1<<i)<=N;i++)
			for(int j=0;(1<<i)+j-1<N;j++)
			{
				if(S[Max[j][i-1]]<S[Max[j+(1<<i-1)][i-1]])
				{
					Max[j][i]=Max[j+(1<<i-1)][i-1];
				}else{
					Max[j][i]=Max[j][i-1];
				}
				
				if(S[Min[j][i-1]]<S[Min[j+(1<<i-1)][i-1]])
				{
					Min[j][i]=Min[j][i-1];
				}else{
					Min[j][i]=Min[j+(1<<i-1)][i-1];
				}
			}
	}
	
	static int queryMax(int l,int r)
	{
		int k=(int)(Math.log(r-l+1)/Math.log(2));
		if(S[Max[l][k]]<S[Max[r-(1<<k)+1][k]])
		{
			return Max[r-(1<<k)+1][k];
		}else{
			return Max[l][k];
		}
	}
	
	static int queryMin(int l,int r)
	{
		int k=(int)(Math.log(r-l+1)/Math.log(2));
		if(S[Min[l][k]]>S[Min[r-(1<<k)+1][k]])
		{
			return Min[r-(1<<k)+1][k];
		}else{
			return Min[l][k];
		}
	}
	
	/**
	 * @param args
	 */
	public static void main(String[] args) throws Exception{

		init();
		System.out.println(S[queryMax(0, N-1)]);
		System.out.println(S[queryMin(0, N-1)]);
		
	}

}
